Trong lý thuyết độ phức tạp, bài toán về tính nguyên tố được gọi đơn giản là bài toán nguyên tố. Dễ thấy rằng nó là coNP: bài toán ngược của nó, bài toán hợp số là NP.

Năm 1975, Vaughan Pratt nhận thấy rằng tồn tại các thuật toán kiểm tra tính nguyên tố trong thời gian đa thức, và như vậy PRIMES là NP, và do đó thuộc về NP ∩ coNP.

Vào năm 2002, Manindra Agrawal, Nitin Saxena và Neeraj Kayal đề xuất một giải thuật tất định kiểm tra tính nguyên tố, là kiểm tra AKS, có khả năng chạy trong O((log n)12). Thế cho nên PRIMES là P.